package main

import "fmt"

func heapSort(inList []int) (outList []int) {
	listLength := len(inList)
	for j := listLength; j > 0; j-- {
		depth := j/2 - 1
		down := listLength - j
		for i := depth; i >= 0; i-- {
			topMax := i + down
			leftChild := 2*i + 1 + down
			rightChild := 2*i + 2 + down

			if leftChild <= listLength-1 && inList[leftChild] > inList[topMax] {
				topMax = leftChild
			}
			if rightChild <= listLength-1 && inList[rightChild] > inList[topMax] {
				topMax = rightChild
			}
			if topMax != i {
				inList[topMax], inList[i+down] = inList[i+down], inList[topMax]
			}
		}
		fmt.Println(inList)
	}

	return inList
}

//HeapQuickSort ...
func HeapQuickSort(inList []int, listLength int) {
	depth := listLength/2 - 1
	for i := depth; i >= 0; i-- {
		topMax := i
		leftChild := 2*i + 1
		rightChild := 2*i + 2

		if leftChild <= listLength-1 && inList[leftChild] > inList[topMax] {
			topMax = leftChild
		}
		if rightChild <= listLength-1 && inList[rightChild] > inList[topMax] {
			topMax = rightChild
		}
		if topMax != i {
			inList[topMax], inList[i] = inList[i], inList[topMax]
		}
	}
}

//HeapSort ..
func HeapSort(inList []int) {
	listLength := len(inList)
	for i := 0; i < listLength; i++ {
		HeapQuickSort(inList, listLength-i)
		fmt.Println("befroe", inList)
		if i < listLength {
			inList[0], inList[listLength-i-1] = inList[listLength-i-1], inList[0]
		}
		fmt.Println("after", inList)
	}
}

func main() {
	inList := []int{4, 21, 567, 12, 67, 1, 0, 3, 324, 12, 998, 45}
	// inList := []int{2, 7, 4, 3, 0, 1}
	// outList := selectSrot(inList)
	// outList := heapSort(inList)
	HeapSort(inList)
	// fmt.Println(outList)
}
